package com.sicheng.lc.周赛.分类.离散化;

import java.util.HashSet;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/7 14:55
 */
public class 每一个查询的最大美丽值 {
    //https://leetcode.cn/problems/most-beautiful-item-for-each-query/
    static int N = (int) 1e5;
    static int n = 5 * N;
    static int[] tree = new int[n + 1];


    void add(int x, int v) {
        for (int i = x; i <= n; i += i & -i) {
            tree[i] = Math.max(tree[i], v);
        }
    }

    int query(int x) {
        int max = -1;
        for (int i = x; i > 0; i -= i & -i) {
            max = Math.max(max, tree[i]);
        }
        return max;
    }

    public int[] maximumBeauty(int[][] items, int[] queries) {
        HashSet<Integer> set = new HashSet<>();
        for (int[] item : items) {
            set.add(item[0]);
        }
        for (int query : queries) {
            set.add(query);
        }

        int[] all = set
                .stream()
                .sorted()
                .mapToInt(k -> k)
                .toArray();


        for (int[] item : items) {
            int x = leftBinarySearch(all, item[0]);
            add(x, item[1]);
        }

        for (int i = 0; i < queries.length; i++) {
            int x = leftBinarySearch(all, queries[i]);
            queries[i] = query(x);
        }

        return queries;
    }

    int leftBinarySearch(int[] nums, int x) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (nums[mid] >= x) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return l + 1;
    }
}
